package CH01数组结构.LeetCode单调队列;

import java.util.ArrayDeque;
import java.util.Deque;

public class LC1425 {
    public int constrainedSubsetSum(int[] nums, int k) {
        int n = nums.length;
        int[] f = new int[n];
        Deque<Integer> queue = new ArrayDeque<>();
        queue.offerLast(0);
        int ans = nums[0];
        f[0] = nums[0];
        for (int i = 1; i < n; i++) {
            while (!queue.isEmpty() && i - queue.peekFirst() > k) {
                queue.removeFirst();
            }
            f[i] = nums[i] + Math.max(f[queue.peekFirst()],0);
            ans = Math.max(ans, f[i]);
            while (!queue.isEmpty() && f[i] >= f[queue.peekLast()]) {
                queue.removeLast();
            }
            queue.addLast(i);
        }
        return ans;
    }
}